#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
int dp[maxn], isp[maxn][maxn];
int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int T; cin >> T;
    while(T--) {
        string s; cin >> s;
        memset(isp, 0, sizeof(isp));
        for (int m = 0; m < s.size(); ++m) {
            isp[m][m] = true;
            int l = m-1, r = m+1;
            while(l>=0 && r < s.size()){
                if(s[l] == s[r]) isp[l][r] = true;
                else break;
                l--, r++;
            }

            l = m, r = m+1;
            while(l>=0 && r < s.size()){
                if(s[l] == s[r]) isp[l][r] = true;
                else break;
                l--, r++;
            }
        }
        dp[0] = 1;
        for (int i = 1; i < s.size(); ++i) {
            if(isp[0][i]) {dp[i] = 1; continue;}
            else dp[i] = i+1;
            for (int j = 0; j < i; ++j) {
                if(isp[j+1][i]) dp[i] = min(dp[i], dp[j] + 1);
            }
        }
        cout << dp[s.size()-1] << endl;
    }
    return 0;
}